{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Constrained NLP \n",
    "## Introduction \n",
    "Recall that in constrained NLP, the objective is to find the optimal value (maximum or minimum) of an objective function, subject to a set of constraints, where at least one function is not linear. \n",
    "In this section, we will present the canonical form for non-linear problems, and use this form to introduce the Kuhn-Tucker conditions, which are a set of conditions that the optimal value must hold.  \n",
    "\n",
    "## Canonical Form\n",
    "The canonical form of a **minimisation** problem is defined as: \n",
    "\n",
    "$\\min f(x)$\n",
    "\n",
    "$\\text{s.t.}$\n",
    "\n",
    "$g_i(x) \\geq 0 \\quad \\forall i = 1, ..., m$\n",
    "\n",
    "where $x = [x_1, x_2, ..., x_n]$ is an array with the n different decision variables of the problem, $f(x)$ is the (non-linear) objective function and $g_i(x)$ are the (non-linear) functions of the left hand sides of the m constraints.\n",
    "Note that in this canonical form, all the constraints are of type *less or equal* and all the right hand sides are 0. It is not required that all the constraints are of the same type, but for now, we will use this definition without loss of generality to present the Kuhn-Tucker conditions.\n",
    "\n",
    "Similarly, the canonical form of a **maximisation** problem is defined as: \n",
    "\n",
    "$\\max f(x)$\n",
    "\n",
    "$\\text{s.t.}$\n",
    "\n",
    "$g_i(x) \\leq 0 \\quad \\forall i = 1, ..., m$\n",
    "\n",
    "Note that, besides that and the fact that the type of optimisation function (which is obviously of type maximise) is different, the canonical form is the same as for minimisation problems. \n",
    "\n",
    "## Kuhn Tucker Conditions\n",
    "The Kuhn-Tucker (KT) conditions provide a set of differential equations that can be used to find the optimal value of a constrained NLP, based on the **Lagrangian** defined below:\n",
    "\n",
    "### Lagrangian\n",
    "Given an optimisation problem with m constraints in the canonical form, let us define the **Lagrangian** function as: \n",
    "\n",
    "$\\text{L}(x,\\lambda) =  f(x) + \\sum_{i=1}^{m}{\\lambda_i*g_i(x)}$\n",
    "\n",
    "That is, to take into account the constraints in the objective function, we add the corresponding functions on the right hand side multiplied by a set of coefficients noted as $\\lambda_i$ which are known as Lagrangian multipliers.\n",
    "\n",
    "### Gradient condition\n",
    "Now, for any candidate solution to be an optimal solution, we know that, as for unconstrained NLP, it must be a critical point and thus satisfy: \n",
    "\n",
    "$\\nabla_x \\text{L}(x,\\lambda) = 0$\n",
    "\n",
    "That is, since each component of the gradient is the first order derivative of the corresponding decision variable, the Lagrangian must satisfy: \n",
    "\n",
    "$\\frac{\\delta \\text{L}}{\\delta x_j} = 0 \\quad \\forall j = [1, ..., n]$\n",
    "\n",
    "### Feasibility condition \n",
    "Additionally, we must ensure that the solution is **feasible**, i.e. that meets all the constraints. Therefore, the feasibility condition yields: \n",
    "\n",
    "$g_i(x) \\leq 0 \\quad \\forall i = [1, ..., m]$\n",
    "\n",
    "Note that, given the expression of the Lagrangian, this is equivalent to: \n",
    "\n",
    "$\\frac{\\delta \\text{L}}{\\delta \\lambda_i}g_i(x) \\leq 0 \\quad \\forall i = [1, ..., m]$\n",
    "\n",
    "### Orthogonality condition\n",
    "Now, note that for the Lagrangian and the objective function to represent exactly the point of the function, at the optimal value, the following conditions must be met: \n",
    "\n",
    "$\\lambda_i*g_i(x)=0 \\quad \\forall i = [1, ..., m]$\n",
    "\n",
    "That is, either the Lagrangian multiplier is equal to zero or the corresponding right hand side is equal to zero.\n",
    "\n",
    "### Non-positive, non-negativity conditions\n",
    "Once that the problem is in the canonical form, we also need to check that the Lagrangian multipliers have the correct size, that is, that they are non-negative or non-positive depending on the type of optimisation function and the type of constraint.\n",
    "The following table summarizes the conditions for **minimization problems**:\n",
    "\n",
    "| i-th constraint type |    Minimization    |    Maximization    |\n",
    "|:--------------------:|:------------------:|:------------------:|\n",
    "|        $\\leq$        | $\\lambda_i \\geq 0$ | $\\lambda_i \\leq 0$ |\n",
    "|         $=$          |    unrestricted    |    unrestricted    |\n",
    "|        $\\geq$        | $\\lambda_i \\leq 0$ | $\\lambda_i \\geq 0$ |\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}